﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GenericGA.reader.tree
{
    /// <summary>
    /// The template which describes a tree to read.
    /// </summary>
    /// <typeparam name="N">The base class type of all the nodes in the tree.</typeparam>
    public class TreeTemplate <N> where N : class
    {

        /// <summary>
        /// Delegate for the methods which make actual node instances out of child nodes.
        /// </summary>
        /// <param name="children">The child nodes of the node.</param>
        /// <param name="reader">A reader object.</param>
        /// <returns>An actual node instance.</returns>
        public delegate N NodeMaker(List<N> children, Reader reader);

        /// <summary>
        /// A set of template types which restrict which node can be connected to which other node.
        /// </summary>
        private HashSet<string> types;

        /// <summary>
        /// The template type of the root node of the tree.
        /// </summary>
        private string rootType;

        /// <summary>
        /// A dictionary which maps template types to nodes of that template type.
        /// </summary>
        private Dictionary<string, List<NodeTemplate<N>>> nodes;

        /// <summary>
        /// Constructor to create a tree template.
        /// </summary>
        /// <param name="typeList">
        /// An array of strings listing all the template types in use. Any nodes using undeclared types will cause an UndeclaredTypeException.
        /// For example an "IF" statement node is itself of type "statement" whilst it's children would be of type "boolean" and type "statement". If a "less than" node is of type "boolean" than it can be a child of the "IF" node.
        /// </param>
        /// <param name="rootType">The template type of the root node.</param>
        /// <param name="nodeList">An array of node templates.</param>
        public TreeTemplate(string[] typeList, string rootType, NodeTemplate<N>[] nodeList)
        {
            this.types = new HashSet<string>(typeList);

            //Set root
            if (!this.types.Contains(rootType))
            {
                throw new UndeclaredTypeException(rootType);
            }
            this.rootType = rootType;
            
            //Initialize node dictionary
            this.nodes = new Dictionary<string, List<NodeTemplate<N>>>();
            foreach (string type in typeList)
            {
                this.nodes.Add(type, new List<NodeTemplate<N>>());
            }
            
            //Put each node in the node dictionary according to its type
            foreach (NodeTemplate<N> node in nodeList)
            {
                //Add the node to every type it belongs to in the dictionary, making sure all of its types are declared types
                foreach (string nodeType in node.NodeTypes)
                {
                    if (!this.types.Contains(nodeType))
                    {
                        throw new UndeclaredTypeException(nodeType);
                    }
                    else
                    {
                        this.nodes[nodeType].Add(node);
                    }
                }

                //Check that every child type of the node is a declared type
                foreach (string childType in node.ChildTypes)
                {
                    if (!this.types.Contains(childType))
                    {
                        throw new UndeclaredTypeException(childType);
                    }
                }
            }

            //Check that every type is associated to a node
            foreach (string type in typeList)
            {
                if (this.nodes[type].Count == 0)
                {
                    throw new NodelessTypeException(type);
                }
            }
        }

        /// <summary>
        /// A class for connecting nodes to their child nodes temporarily whilst building the breadth first tree.
        /// </summary>
        public class PseudoNode
        {
            
            /// <summary>
            /// The node which is to be connected to child nodes.
            /// </summary>
            public NodeTemplate<N> node;
            
            /// <summary>
            /// The child nodes of the node.
            /// </summary>
            public List<PseudoNode> children;

            /// <summary>
            /// Create a pseudo node which does not have any children at the time.
            /// </summary>
            /// <param name="node">The node to be connected.</param>
            public PseudoNode(NodeTemplate<N> node)
            {
                this.node = node;
                this.children = new List<PseudoNode>();
            }

        }

        /// <summary>
        /// Generate an actual tree.
        /// </summary>
        /// <param name="reader">A reader object.</param>
        /// <param name="maxNodes">A dictionary which tells the maximum number of nodes to be used for each template type of node, before the default children are resorted to.</param>
        /// <returns>The root of the tree.</returns>
        public N Generate(Reader reader, Dictionary<string, int> maxNodes)
        {
            //Reader a pseudo tree
            PseudoNode pseudoRoot = ReadPseudoTree(reader, maxNodes);

            //Construct the actual tree from the pseudo tree
            N actualRoot = BuildTree(pseudoRoot, reader);

            return actualRoot;
        }

        /// <summary>
        /// Read a pseudo tree.
        /// </summary>
        /// <param name="reader">A reader object.</param>
        /// <param name="maxNodes">A dictionary which tells the maximum number of nodes to be used for each template type of node, before the default children are resorted to.</param>
        /// <returns>The root of the tree.</returns>
        public PseudoNode ReadPseudoTree(Reader reader, Dictionary<string, int> maxNodes)
        {
            //Read a list of nodes to use for each type of node
            Dictionary<string, Queue<NodeTemplate<N>>> nodesToUse = new Dictionary<string, Queue<NodeTemplate<N>>>();
            foreach (string type in types)
            {
                nodesToUse[type] = new Queue<NodeTemplate<N>>(reader.ReadList<NodeTemplate<N>>(maxNodes[type], nodes[type]));
            }

            //Build the tree breadth first using a pseudo tree so that the available nodes to use will be distributed amongst subtrees
            PseudoNode pseudoRoot = new PseudoNode(nodesToUse[rootType].Dequeue());
            Queue<PseudoNode> nodesToAddTo = new Queue<PseudoNode>();
            nodesToAddTo.Enqueue(pseudoRoot);
            while (nodesToAddTo.Count > 0)
            {
                PseudoNode currNode = nodesToAddTo.Dequeue();

                //Add children to current node, using null when no more nodes of the required type are left.
                foreach (string childType in currNode.node.ChildTypes)
                {
                    PseudoNode child;
                    if (nodesToUse[childType].Count > 0)
                    {
                        child = new PseudoNode(nodesToUse[childType].Dequeue());
                        nodesToAddTo.Enqueue(child);
                    }
                    else
                    {
                        child = null;
                    }
                    currNode.children.Add(child);
                }
            }

            return pseudoRoot;
        }

        /// <summary>
        /// Build an actual tree from a pseudo tree.
        /// </summary>
        /// <param name="pseudoRoot">The root of the pseudo tree.</param>
        /// <param name="reader">A reader object.</param>
        /// <returns>The root of the actual tree.</returns>
        public N BuildTree(PseudoNode pseudoRoot, Reader reader)
        {
            List<N> actualChildren = new List<N>();
            foreach (PseudoNode child in pseudoRoot.children)
            {
                if (child == null)
                {
                    actualChildren.Add((N)null);
                }
                else
                {
                    actualChildren.Add(BuildTree(child, reader));
                }
            }
            return pseudoRoot.node.CreateNode(actualChildren, reader);
        }

    }
}
